#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Software: PyCharm
# @Version : Python-
# @Author  : Shengji He
# @Email   : hsjbit@163.com
# @File    : CombinationSum3.py
# @Time    : 2020/9/11 11:21
# @Description:
from typing import List


class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        """
        Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9
        can be used and each combination should be a unique set of numbers.

        Note:
            - All numbers will be positive integers.
            - The solution set must not contain duplicate combinations.
        Example 1:
            Input: k = 3, n = 7
            Output: [[1,2,4]]
        Example 2:
            Input: k = 3, n = 9
            Output: [[1,2,6], [1,3,5], [2,3,4]]

        :param k:
        :param n:
        :return:
        """
        ans = []
        c = self.uniqueCombinations([i for i in range(1, 10)], k)
        while True:
            try:
                num = next(c)
                if sum(num) == n:
                    ans.append(num)
            except StopIteration:
                break
        return ans

    def uniqueCombinations(self, items, n):
        def afterIthItem(items, i):
            return items[i + 1:]
        return self.__combinators(afterIthItem, items, n)

    def __combinators(self, _handle, items, n):
        if n == 0:
            yield []
        for i, item in enumerate(items):
            this_one = [item]
            for cc in self.__combinators(_handle, _handle(items, i), n - 1):
                yield this_one + cc


if __name__ == '__main__':
    S = Solution()
    k = 3
    n = 9
    print(S.combinationSum3(k, n))
    print('done')
